\part{集合论}

特别需要说明的是,本部分所讲述的集合论并非公理化集合论

\chapter{集合代数}

\section{集合的基本概念}

\begin{itementry}
    集合的表示法:列元素表示法;谓词表示法
    \begin{subentry}
        特别地,为了体系的严谨,规定对任何集合\(A\),都有\(A\notin A\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    子集:设\(A,B\)是集合,若\(B\)中的每个元素都是\(A\)中的元素,则称\(B\)是\(A\)的子集,也称\(B\)被\(A\)包含或\(A\)包含\(B\),记为\(B\subseteq A\).若\(B\)不被\(A\)包含,则记为\(B\not\subseteq A\)
    \begin{subentry}
        即:\(B\subseteq A:=\forall x(x\in B\to x\in A)\)\par
        特别地,隶属关系(\(\in\))和包含关系(\(\subseteq\))都是两个集合之间的关系,对于某些集合这两种关系可以同时成立
    \end{subentry}
\end{itementry}

\begin{itementry}
    相等:设\(A,B\)为集合,若\(A\subseteq B\)且\(B\subseteq A\),则称\(A\)与\(B\)相等,记为\(A=B\).若\(A\)与\(B\)不相等,则记为\(A\neq B\).\par
    即:\(A=B:=(A\subseteq B)\wedge (B\subseteq A)\)
\end{itementry}

\begin{itementry}
    真子集:设\(A,B\)为集合,若\(B\subseteq A\wedge B\neq A\),则称\(B\)是\(A\)的真子集,记为\(B\subset A\).若\(B\)不是\(A\)的真子集,则记为\(B\not\subset A\)
    \begin{subentry}
        即:\(B\subset A:=B\subseteq A\wedge B\neq A\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    空集:不含任何元素的集合称为空集,记为\(\emptyset\).
    \begin{subentry}
        即:\(\emptyset:=\{x\mid x\neq x\}\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    定理:空集是一切集合的子集
\end{itementry}

\begin{itementry}
    \(n\)元集\&\(m\)元子集:含有\(n\)个元素的集合称为\(n\)元集,其含有\(m(m\leq n)\)个元素的子集称为它的\(m\)元子集
\end{itementry}

\begin{itementry}
    幂集:设\(A\)为集合,将\(A\)的全体子集构成的集合称为\(A\)的幂集,记为\(P(A)\),\(\mathscr{P}A\)或\(2^{A}\).
    \begin{subentry}
        即:\(P(A):=\{x\mid x\subseteq A\}\)\par
        特别地,若\(A\)是\(n\)元集,则\(P(A)\)有\(2^n\)个子集
    \end{subentry}
\end{itementry}

\begin{itementry}
    全集:在某个具体问题中,若设计的所有集合都是某个集合的子集,则称这个集合为全集,记为\(E\)
\end{itementry}

\section{集合的运算}

\begin{itementry}
    并集\&交集\&相对补集:设\(A,B\)为集合,则我们将
    \begin{align*}
        A\cup B=\{x\mid x\in A\vee x\in B\}\\
        A\cap B=\{x\mid x\in A\wedge x\in B\}\\
        A-B=\{x\mid x\in A\wedge x\notin B\}
    \end{align*}
    分别成为\(A\)与\(B\)的并集,交集与相对补集
\end{itementry}

\begin{itementry}
    不交:若两个集合的交集为空集,则称这两个集合不交
\end{itementry}

\begin{itementry}
    \(n\)个集合的并和交:
    \begin{align*}
        \bigcup^n_{i=1}A_i=A_1\cup A_2\cup\cdots\cup A_n\\
        \bigcap^n_{i=1}A_i=A_1\cap A_2\cap\cdots\cap A_n
    \end{align*}
\end{itementry}

\begin{itementry}
    对称差集:设\(A,B\)为集合,\(A\)与\(B\)的对称差集\(A\oplus B\)定义为:\(A\oplus B=(A-B)\cup(B-A)=(A\cup B)-(A\cap B)\)
\end{itementry}

\begin{itementry}
    绝对补集:在给定全集\(E\)之后,\(A\subseteq E\),\(A\)的绝对补集\(\sim A\)定义为\(\sim A=E-A=\{x\mid x\in E\wedge x\notin A\}\)
\end{itementry}

\begin{itementry}
    广义并:设\(A\)为集合,\(A\)的元素的元素构成的集合称为\(A\)的广义并,记为\(\cup A\)
    \begin{subentry}
        即:\(\cup A:=\{x\mid \exists y(y\in A\wedge x\in y)\}\)\par
        特别地,若\(A=\{A_1,\dots,A_n\}\),则\(\cup A=A_1\cup\cdots\cup A_n\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    广义交:设\(A\)为非空集合,\(A\)的所有元素的公共元素构成的集合称为\(A\)的广义交,记为\(\cap A\)
    \begin{subentry}
        即:\(\cap A:=\{x\mid \forall y(y\in A\to x\in y)\}\).\par
        特别地,若\(A=\{A_1,\dots,A_n\}\),则\(\cap A=A_1\cap\cdots\cap A_n\).空集没有广义交
    \end{subentry}
\end{itementry}

\begin{itementry}
    集合运算顺序:
    \begin{subentry}
        称广义并,广义交,幂集,绝对补运算为一类运算\par
        并,交,相对补,对称差运算为二类运算\par
        一类运算优先于二类运算\par
        一类运算之间由右向左顺序进行\par
        二类运算之间由括号决定先后顺序
    \end{subentry}
\end{itementry}

\section{有穷集的计数}

\begin{itementry}
    元素个数:设\(A\)为一集合,若\(A\)有\(n\)个元素,则记为\(|A|=n\)
\end{itementry}

\begin{itementry}
    包含容斥原理:设\(S\)为有穷集,\(P_1,\dots,P_n\)是\(n\)个性质,\(S\)中的任何元素\(x\)或者具有性质\(P_i\),或者不具有性质\(P_i\).用\(A_i\)表示\(S\)中具有性质\(P_i\)的元素构成的子集,则\(S\)中不具有性质\(P_1,\dots,P_n\)的元素数为
    \begin{gather*}
        |\overline{A_1}\cap\cdots\cap\overline{A_n}=|S|-\sum^n_{i=1}|A_i|+\sum_{1\leq i<j\leq n}|A_i\cap A_j|\\-\sum_{1\leq i<j<k\leq n}|A_i\cap A_j\cap A_k|+\cdots+(-1)^n|A_1\cap \cdots\cap A_n|
    \end{gather*}
\end{itementry}

\section{集合恒等式}

\begin{itementry}
    幂等律:\(A\cup A=A;A\cap A=A\)
\end{itementry}

\begin{itementry}
    结合律:
    \(\begin{aligned}[t]
        &(A\cup B)\cup C=A\cup(B\cup C)\\
        &(A\cap B)\cap C=A\cap(B\cap C)
    \end{aligned}\)
\end{itementry}

\begin{itementry}
    交换律:\(A\cup B=B\cup A;A\cap B=B\cap A\)
\end{itementry}

\begin{itementry}
    分配律:
    \(\begin{aligned}[t]
        &A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\\
        &A\cap(B\cup C)=(A\cap B)\cup(A\cap C)
    \end{aligned}\)
\end{itementry}

\begin{itementry}
    同一律:\(A\cup\emptyset=A,A\cap E=A\)
\end{itementry}

\begin{itementry}
    零率:\(A\cup E=E,A\cap\emptyset=\emptyset\)
\end{itementry}

\begin{itementry}
    排中律:\(A\cup\sim A=E\)
\end{itementry}

\begin{itementry}
    矛盾律:\(A\cap\sim A=\emptyset\)
\end{itementry}

\begin{itementry}
    吸收律:\(A\cup(A\cap B)=A;A\cap(A\cup B)=A\)
\end{itementry}

\begin{itementry}
    德摩根率:
    \(\begin{aligned}[t]
        &A-(B\cup C)=(A-B)\cap(A-C)\\
        &A-(B\cap C)=(A-B)\cup(A-C)
    \end{aligned}\)
\end{itementry}

\begin{itementry}
    双重否定率:\(\sim\sim A=A\)
\end{itementry}

\chapter{二元关系}

\section{有序对与笛卡尔积}

\begin{itementry}
    有序对/序偶:两个元素\(x,y\)(允许\(x=y\))按照一定顺序构成的二元组称为一个有序对或序偶,记为\(\left<x,y\right>\),其中\(x\)称为其第一元素,\(y\)称为其第二元素
\end{itementry}

\begin{itementry}
    笛卡尔积:设\(A,B\)为集合,用\(A\)中的元素为第一元素,\(B\)中的元素为第二元素构成有序对.所有这样的有序对组成的集合称作笛卡尔积,记作\(A\times B\).
    \begin{subentry}
        即:\(A\times B:=\{\left<x,y\right>\mid x\in A\wedge y\in B\}\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    笛卡尔积的性质:
    \begin{theitem}
        \item 对任意集合\(A\),有\(A\times\emptyset=\emptyset;\emptyset\times A=\emptyset\)
        \item 一般来说,笛卡尔积运算不满足交换律,即
        \begin{align*}
            A\times B\neq B\times A(A\neq\emptyset\wedge B\neq\emptyset\wedge A\neq B)
        \end{align*}
        \item 笛卡尔积运算不满足结合律,即
        \begin{align*}
            (A\times B)\times C\neq A\times(B\times C)(A,B,C\neq\emptyset)
        \end{align*}
        \item 笛卡尔积运算对并和交满足分配律,即:
        \begin{align*}
            A\times(B\cup C)=(A\times B)\cup(A\times C)\\
            A\times(B\cap C)=(A\times B)\cap(A\times C)\\
            (B\cup C)\times A=(B\times A)\cup(C\times A)\\
            (B\cap C)\times A=(B\times A)\cap(C\times A)
        \end{align*}
        \item \(A\subseteq C\wedge B\subseteq D\Rightarrow A\times B\subseteq C\times D\)
    \end{theitem}
\end{itementry}

\section{二元关系}

\begin{itementry}
    二元关系:若一个非空集合满足以下条件之一:
    \begin{theitem}
        \item 集合非空,且其元素都是有序对
        \item 集合是空集
    \end{theitem}
    则称该集合为一个二元关系,记为\(R\).二元关系也简称为关系.对于关系\(R\),若\(\left<x,y\right>\in R\),则记为\(xRy\),否则记为\(x/\hspace{-0.55em}Ry\)
\end{itementry}

\begin{itementry}
    \(A\)到\(B\)的二元关系\&\(A\)上的二元关系:设\(A,B\)为集合,\(A\times B\)的任何子集所定义的二元关系称为从\(A\)到\(B\)的二元关系.\hspace*{-0.5em}
    \begin{subentry}
        特别地,当\(A=B\)时,称为\(A\)上的二元关系
    \end{subentry}
\end{itementry}

\begin{itementry}
    空关系:对于任何集合\(A\),\(\emptyset\)是\(A\)上的关系,称为空关系
\end{itementry}

\begin{itementry}
    全域关系\&恒等关系:对任意集合\(A\),我们分别称
    \begin{gather*}
        E_A=\{\left<x,y\right>\mid x\in A\wedge y\in A\}=A\times A\\
        I_A=\{\left<x,x\right>\mid x\in A\}
    \end{gather*}
    为\(A\)上的全域关系与恒等关系
\end{itementry}

\begin{itementry}
    小于等于关系\&整除关系\&包含关系:对于集合\(A\),我们分别称
    \begin{gather*}
        L_A=\{\left<x,y\right>\mid x,y\in A,x\leq y\}\\
        D_A=\{\left<x,y\right>\mid x,y\in A,x\mid y\}\\
        R_{\subseteq}=\{\left<x,y\right>\mid x,y\in A,x\subseteq y\}
    \end{gather*}
    为\(A\)上的小于等于关系,整除关系与包含关系
\end{itementry}

\begin{itementry}
    关系的表达法:
    \begin{theitem}
        \item 集合表达法:即\(R=\{\left<x,y\right>\mid\dots\}\)
        \item 关系矩阵:设\(A=\{x_1,\dots,x_n\}\),\(R\)是\(A\)上的关系,令\(\delta_{ij}=
        \begin{cases}
            1,&\text{若}x_iRx_j\\
            0,&\text{若}x_i/\hspace{-0.55em}Rx_j
        \end{cases}\)
            (常称为特征函数),则我们称\(\mathbf{M}_R=(\delta_{ij})_{n\times n}\)为\(R\)的关系矩阵
        \item 关系图:见原书,略
    \end{theitem}
\end{itementry}

\section{关系的运算}

\begin{itementry}
    定义域:设\(R\)是二元关系,\(R\)中所有有序数对的第一元素构成的集合称为\(R\)的定义域,记为\(\dom R\)
    \begin{subentry}
        即:\(\dom R:=\{x\mid\exists y\left<x,y\right>\in R\}\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    值域:设\(R\)是二元关系,\(R\)中所有有序对的第二元素构成的集合称作\(R\)的值域,记为\(\ran R\)
    \begin{subentry}
        即:\(\ran R:=\{y\mid\exists x\left<x,y\right>\in R\}\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    域:\(R\)的定义域和值域的并集称为\(R\)的域,记为\(\fld R\)
    \begin{subentry}
        即:\(\fld R=\dom R\cup\ran R\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    逆关系:设\(R\)为二元关系,将其第一元素第二元素互换得到的关系称为\(R\)的逆关系,记为\(R^{-1}\)
    \begin{subentry}
        即:\(R^{-1}:=\{\left<x,y\right>\mid\left<y,x\right>\in R\}\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    右复合:设\(F,G\)为二元关系,则我们称\(F\circ G=\{\left<x,y\right>\mid\exists t(\left<x,t\right>\in F\wedge\left<t,y\right>\in G)\}\)为\(F\)与\(G\)的右复合,记为\(F\circ G\)
\end{itementry}

\begin{itementry}
    限制:设\(R\)为二元关系,\(A\)为集合,则我们把\(R\)中以\(A\)的元素为第一元素的所有元素所构成的集合称为\(A\)上的限制,记为\(R\upharpoonright A\)
    \begin{subentry}
        即:\(R\upharpoonright A:=\{\left<x,y\right>\mid xRy\wedge x\in A\}\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    像:设\(R\)为二元关系,\(A\)为集合,则我们将\(A\)在\(R\)上的限制的值域称为像,记为\(R[A]\)
    \begin{subentry}
        即:\(R[A]:=\ran(R\upharpoonright A)\)\par
        特别地,在本节所定义的这些运算中,一元运算优先于其余运算,二元运算优先于集合运算,且下文中我将会使用括号注明
    \end{subentry}
\end{itementry}

\begin{itementry}
    定理:设\(F,G,H\)是任意关系,\(R\)为\(A\)上关系,\(B,C\)为集合,则:
    \begin{theitem}
        \iitem \((F^{-1})^{-1}=F\)
        \iitem \(\dom(F^{-1})=\ran F,\ran(F^{-1})=\dom F\)
        \iitem \((F\circ G)\circ H=F\circ(G\circ H)\)
        \iitem \((F\circ G)^{-1}=F^{-1}\circ G^{-1}\)
        \iitem \(R\circ I_A=I_A\circ R=R\)
        \iitem \(F\circ (G\cup H)=(F\circ G)\cup(F\circ H)\)
        \iitem \((F\cup G)\circ H=(F\circ H)\cup(G\circ H)\)
        \iitem \(F\circ (G\cap H)\subseteq(F\circ G)\cap(F\circ H)\)
        \iitem \((F\cap G)\circ H\subseteq(F\circ H)\cap(G\circ H)\)
        \iitem \(F\upharpoonright(B\cup C)=(F\upharpoonright B)\cup(F\upharpoonright C)\)
        \iitem \(F\upharpoonright(B\cap C)\subseteq(F\upharpoonright B)\cap(F\upharpoonright C)\)
        \iitem \(F[B\cup C]=F[B]\cup F[C]\)
        \iitem \(F[B\cap C]\subseteq F[B]\cap F[C]\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    幂:设\(R\)为\(A\)上的关系,\(n\)为自然数,则\(R\)的\(n\)次幂\(R^n\)定义为:\par
    \begin{theitem}
        \item \(R^0=\{\left<x,x\right>\mid x\in A\}=I_A\)
        \item \(R^{n+1}=R^n\circ R\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(R\)为\(A\)上关系,若存在自然数\(s,t(s<t)\),使得\(R^s\*=\*E^t\),那么就有
    \begin{theitem}
        \item 对任何\(k\in\NN\),有\(R^{s+k}=R^{t+k}\)
        \item 对任何\(k,i\in\NN\),有\(R^{s+kp+i}=E^{s+i}\),其中\(p=t-s\)
        \item 令\(S=\{R^0,\cdots,R^{t-1}\}\),则\(\forall q\in \NN,R^q\in S\)
    \end{theitem}
\end{itementry}

\section{关系的性质}

\begin{itementry}
    自反性:设\(R\)为\(A\)上的关系,若\(\forall x(x\in A\to\left<x,x\right>\in R)\),则称\(R\)在\(A\)上自反
\end{itementry}

\begin{itementry}
    反自反性:设\(R\)为\(A\)上的关系,若\(\forall x(x\in A\to\left<x,x\right>\notin R)\),则称\(R\)在\(A\)上反自反
\end{itementry}

\begin{itementry}
    对称性:设\(R\)为\(A\)上的关系,若\(\forall x\forall y(x,y\in A\wedge\left<x,y\right>\in R\to\left<y,x\right>\in R)\),则称\(R\)在\(A\)上对称
\end{itementry}

\begin{itementry}
    反对称性:设\(R\)为\(A\)上关系,若\(\forall x\forall y(x,y\in A\wedge\left<x,y\right>\in R\wedge\left<y,x\right>\to x=y)\),则称\(R\)在\(A\)上反对称
\end{itementry}

\begin{itementry}
    传递性:设\(R\)为\(A\)上的关系,若\(\forall x\forall y\forall z(x,y,z\in A\wedge\left<x,y\right>\in R\wedge\left<y,z\right>\in R\to\left<x,z\right>\in R)\),则称\(R\)在\(A\)上传递
\end{itementry}

\begin{itementry}
    定理:五种性质的充要条件:设\(R\)为\(A\)上的关系,则:
    \begin{theitem}
        \item 集合表达式中
        \begin{theitem}
            \item[(1)] \(R\)在\(A\)上自反当且仅当\(I_A\subseteq R\)
            \item[(2)] \(R\)在\(A\)上反自反当且仅当\(R\cap I_A=\emptyset\)
            \item[(3)] \(R\)在\(A\)上对称当且仅当\(R=R^{-1}\)
            \item[(4)] \(R\)在\(A\)上反对称当且仅当\(R\cap R^{-1}\subseteq I_A\)
            \item[(5)] \(R\)在\(A\)上传递当且仅当\(R\circ R\subseteq R\)
        \end{theitem}
        \item[2.] 关系矩阵中:
        \begin{theitem}
            \item[(1)] \(R\)在\(A\)上自反当且仅当\(\mathbf{M}_R\)主对角线元素全为1
            \item[(2)] \(R\)在\(A\)上反自反当且仅当\(\mathbf{M}_R\)主对角线全为0
            \item[(3)] \(R\)在\(A\)上对称当且仅当\(\mathbf{M}_R\)是对称矩阵
            \item[(4)] \(R\)在\(A\)上反对称当且仅当\(\delta_{ij}=1\)且\(i\neq j\)时,有\(\delta_{ji}=0\)
            \item[(5)] \(R\)在\(A\)上传递当且仅当\(R\)的关系矩阵\(M\)满足\(M^2\)中1所在的位置在\(M\)中也都是1
        \end{theitem}
        \item[3.] 在关系图中
        \begin{theitem}
            \item[(1)] \(R\)在\(A\)上自反当且仅当\(R\)的关系图中每个顶点都有环
            \item[(2)] \(R\)在\(A\)上自反当且仅当\(R\)的关系图中每个顶点都没有环
            \item[(3)] \(R\)在\(A\)上对称当且仅当\(R\)的关系图上任意两个顶点间没有单向边
            \item[(4)] \(R\)在\(A\)上反对称当且仅当\(R\)的关系图上任意两个顶点间没有双向边
            \item[(5)] \(R\)在\(A\)上传递当且仅当\(R\)的关系图上若\(x_i\)到\(x_j\)有边,\(x_j\)到\(x_k\)有边,则\(x_i\)到\(x_k\)有边
        \end{theitem}
    \end{theitem}
\end{itementry}

\section{关系的闭包}

\begin{itementry}
    自反闭包/对称闭包/传递闭包:设\(R\)是非空集\(A\)上的关系,\(R\)的自反/对称/传递闭包指\(A\)上的关系\(R'\),使得\(R'\)满足:\par
    \begin{theitem}
        \item \(R'\)是自反/对称/传递的
        \item \(R\subseteq R'\)
        \item 对\(A\)上任何包含\(R\)的自反/对称/传递关系\(R''\),有\(R'\subseteq R''\)
    \end{theitem}
    \begin{subentry}
        特别地,我们将\(R\)的自反/对称/传递闭包分别记为\(r(R),s(R),t(R)\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    定理:设\(R\)为\(A\)上的关系,则
    \begin{theitem}
        \item \(r(R)=R\cup R^0\)
        \item \(s(R)=R\cup R^{-1}\)
        \item \(t(R)=R\cup R^2\cup R^3\cup\cdots\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(R\)为非空集\(A\)上的关系,则:
    \begin{theitem}
        \item \(R\)是自反的当且仅当\(r(R)=R\)
        \item \(R\)是对称的当且仅当\(s(R)=R\)
        \item \(R\)是传递的当且仅当\(t(R)=R\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(R_1\)和\(R_2\)是非空集\(A\)上的关系,\(R_1\subseteq R_2\),则
    \begin{theitem}
        \item \(r(R_1)\subseteq r(R_2)\)
        \item \(s(R_1)\subseteq s(R_2)\)
        \item \(t(R_1)\subseteq t(R_2)\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(R\)是非空集\(A\)上的关系,则:
    \begin{theitem}
        \item 若\(R\)是自反的,则\(s(R)\)与\(t(R)\)也是自反的
        \item 若\(R\)是对称的,则\(r(R)\)与\(t(R)\)也是对称的
        \item 若\(R\)是传递的,则\(r(R)\)是传递的
    \end{theitem}
\end{itementry}

\section{等价关系与划分}

\begin{itementry}
    等价关系:设\(R\)为非空集\(A\)上的关系,若\(R\)是自反,对称,传递的,则称\(R\)为\(A\)上的等价关系.若\(\left<x,y\right>\in R\),则称\(x\)等价于\(y\),记为\(x\sim y\)
\end{itementry}

\begin{itementry}
    等价类:设\(R\)为非空集\(A\)上的等价关系,\(\forall x\in A\),我们令\([x]_R=\{y\mid y\in A\wedge xRy\}\),称为\(x\)关于\(R\)的等价类,简称为\(x\)的等价类,记为\([x]\)或\(\overline{x}\)
\end{itementry}

\begin{itementry}
    定理:设\(R\)为非空集合\(A\)上的等价关系,则
    \begin{theitem}
        \item \(\forall x\in A,[x]\)是\(A\)的非空子集
        \item \(\forall x,y\in A\),若\(xRy\),则\([x]=[y]\)
        \item \(\forall x,y\in A\),若\(x/\hspace{-0.55em}Ry\),则\([x]\)与\([y]\)不交
        \item \(\cup\{[x]\mid x\in A\}=A\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    商集:设\(R\)为非空集\(A\)上的等价关系,以\(R\)的所有等价类的集合称为\(A\)关于\(R\)的商集,记为\(A/R\)
    \begin{subentry}
        即:\(A/R:=\{[x]_R\mid x\in A\}\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    子集族:对于非空集合\(A\),我们将\(A\)的部分子集所构成的集合称为\(A\)的子集族
\end{itementry}

\begin{itementry}
    划分:设\(A\)为非空集,若\(A\)的子集族\(\pi\)满足:
    \begin{theitem}
        \item \(\emptyset\notin\pi\)
        \item \(\forall x\forall y(x,y\in\pi\wedge x\neq y\to x\cap y=\emptyset)\)
        \item \(\cup \pi=A\)
    \end{theitem}
    则称\(\pi\)是\(A\)的一个划分,称\(\pi\)中的元素为\(A\)的划分块
\end{itementry}

\section{偏序关系}

\begin{itementry}
    设\(R\)为非空集\(A\)上的关系,若\(R\)是自反的,对称的和传递的,则称\(R\)为\(A\)上的偏序关系,记为\(\preccurlyeq\)
\end{itementry}

\begin{itementry}
    小于等于:设\(\preccurlyeq\)为\(A\)上的偏序关系,若有\(\left<x,y\right>\in\preccurlyeq\),则称\(x\)小于等于\(y\),记为\(x\preccurlyeq y\)
\end{itementry}

\begin{itementry}
    小于\&可比:设\(\preccurlyeq\)为非空集\(A\)上的偏序关系,定义
    \begin{theitem}
        \item \(\forall x,y\in A,x\prec y\Leftrightarrow x\preccurlyeq y\wedge x\neq y\)
        \item \(\forall x,y\in A\),\(x\)与\(y\)可比\(\Leftrightarrow x\preccurlyeq y\vee y\preccurlyeq x\)
    \end{theitem}
    其中,\(x\prec y\)读作\(x\)小于\(y\)
\end{itementry}

\begin{itementry}
    定理:在\(A\)上的偏序关系\(\preccurlyeq\)下,任意两元素\(x,y\),只有\(x\prec y\)(或\(y\prec x\)),\(x=y\),\(x\)与\(y\)不可比三种中的一种发生
\end{itementry}

\begin{itementry}
    全序关系/线序关系:设\(R\)为非空集\(A\)上的偏序关系,若\(\forall x,y\in A\),\(x\)和\(y\)都是可比的,则称\(R\)为\(A\)上的全序关系(或线序关系)
\end{itementry}

\begin{itementry}
    偏序集:集合\(A\)和\(A\)上的偏序关系\(\preccurlyeq\)一起称作偏序集,记为\(\left<A,\preccurlyeq\right>\)
\end{itementry}

\begin{itementry}
    覆盖:设\(\left<A,\preccurlyeq\right>\)为偏序集,\(\forall x,y\in A\),若\(x\prec y\)且不存在\(z\in A\)是的\(x\prec z\prec y\),则称\(y\)覆盖\(x\)
\end{itementry}

\begin{itementry}
    哈斯图画法:见原书,略
\end{itementry}

\begin{itementry}
    最小元\&最大元\&极小元\&极大元:设\(\left<A,\preccurlyeq\right>\)为偏序集,\(B\subseteq A,y\in B\)
    \begin{theitem}
        \item 若\(\forall x(x\in B\to y\preccurlyeq x)\)成立,则称\(y\)为\(B\)的最小元
        \item 若\(\forall x(x\in B\to x\preccurlyeq y)\)成立,则称\(y\)为\(B\)的最大元
        \item 若\(\forall x(x\in B\wedge x\preccurlyeq y\to x=y)\)成立,则称\(y\)为\(B\)的极小元
        \item 若\(\forall x(x\in B\wedge y\preccurlyeq x\to x=y)\)成立,则称\(y\)为\(B\)的极大元
    \end{theitem}
\end{itementry}

\begin{itementry}
    上界\&下界\&上确界/最小上界\&下确界/最大下界:设\(\left<A,\preccurlyeq\right>\)为偏序集,\(B\subseteq A\),\(y\in A\)
    \begin{theitem}
        \item 若\(\forall x(x\in B\to x\preccurlyeq y)\)成立,则称\(y\)为\(B\)的上界
        \item 若\(\forall x(x\in B\to y\preccurlyeq x)\)成立,则称\(y\)为\(B\)的下界
        \item 令\(C=\{y\mid y\text{为}B\text{的上界}\}\),则称\(C\)的最小元为\(B\)的最小上界或上确界
        \item 令\(C=\{y\mid y\text{为}B\text{的下界}\}\),则称\(C\)的最大元为\(B\)的最大下界或下确界
    \end{theitem}
\end{itementry}

\chapter{函数}

\section{函数的定义与性质}

\begin{itementry}
    函数:设\(F\)为二元关系,若\(\forall x\in\dom F\)都存在唯一的\(y\in\*\ran F\)使\(xFy\)成立,则称\(F\)为函数.对于函数\(F\),若有\(xFy\),则记为\(y=F(x)\),且称\(y\)为\(F\)在\(x\)的值
\end{itementry}

\begin{itementry}
    相等:设\(F,G\)为函数,则\(x=y\Leftrightarrow F\subseteq G\wedge G\subseteq F\)
\end{itementry}

\begin{itementry}
    从\(A\)到\(B\)的函数:设\(A,B\)为函数,若\(f\)为函数,且\(\dom f=A,\*\ran F\subseteq B\),则\(f\)称为从\(A\)到\(B\)的函数,记为\(f:A\to B\)
\end{itementry}

\begin{itementry}
    上:所有从\(A\)到\(B\)的函数集合记为\(B^A\),读作\(B\)上\(A\),记为\(B^A\)
    \begin{subentry}
        即:\(B^A:=\{f\mid f:A\to B\}\)\par
        特别地,若\(|A|=m,|B|=n\),则\(|B^A|=n^m\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    定理:
    \begin{theitem}
        \item \(\emptyset^{\emptyset}=\{\emptyset\}\)
        \item \(A\neq\emptyset,A^{\emptyset}=\{\emptyset\}\)
        \item \(A\neq\emptyset,\emptyset^A=\emptyset\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    像\&完全原像:设函数\(f:A\to B,A_1\subseteq A,B_1\subseteq B\)
    \begin{theitem}
        \item 令\(f(A_1)=\{f(x)\mid x\in A_1\}\),称\(f(A_1)\)为\(A_1\)在\(f\)下的像.
        \begin{subentry}
            特别地,当\(A_1=A\)时,称\(f(A)\)为函数的像
        \end{subentry}
        \item 令\(f^{-1}(B_1)=\{x\mid x\in A\wedge f(x)\in B_1\}\),称\(f^{-1}(B_1)\)为\(B_1\)在\(f\)下的完全原像
    \end{theitem}
\end{itementry}

\begin{itementry}
    满射\&单射\&双射/一一映像:设\(f:A\to B\)
    \begin{theitem}
        \item 若\(\ran f=B\),则称\(f\)为满射
        \item 若\(\forall y\in\ran f\),存在唯一的\(x\in A\),使得\(f(x)=y\),则称\(f\)时单射
        \item 若\(f\)既是单射又是满射,则称\(f\)为双射或一一映像
    \end{theitem}
\end{itementry}

\begin{itementry}
    常函数:设\(f:A\to B\),若存在\(c\in B\)使得对所有的\(x\in A\)都有\(f(x)=c\),则称\(f\)是常函数
\end{itementry}

\begin{itementry}
    恒等函数:我们将\(A\)上满足\(\forall x\in A\),\(f(x)=x\)的函数\(f\)称为恒等函数,记为\(I_A(x)\)(有时记为\(\id_A\))
\end{itementry}

\begin{itementry}
    单调递增\&严格单调递增:设\(\left<A,\preccurlyeq\right>,\left<B,\preccurlyeq\right>\)为偏序集,\(f:A\to B\),若对任意的\(x_1,x_2\in A,x_1\prec x_2\),就有\(f(x_1)\preccurlyeq f(x_2)\),则称\hspace*{-0.3em}\\\(f\)单调递增.若对任意\(x_1,x_2\in A\),\(x_1\prec x_2\)就有\(f(x_1)\prec f(x_2)\),则称\(f\)为严格单调递增的
\end{itementry}

\begin{itementry}
    特征函数:设\(A\)为集合,\(A'\subseteq A\),我们称\(\chi_{A'}:A\to\{0,1\}\)为\(A'\)的特征函数,其中,\(\chi_{A'}(a)=\begin{cases}1,&a\in A'\\0,&a\in A-A'\end{cases}\)
\end{itementry}

\begin{itementry}
    自然映射:设\(R\)是\(A\)上的等价关系,令\(g:A\to A/R,g(a)\*=[a],\forall a\in A\),称\(g\)为\(A\)到商集\(A/R\)的自然映射
\end{itementry}

\section{函数的复合与反函数}

\begin{itementry}
    定理:设\(F,G\),则\(F\circ G\)也是函数,且满足:
    \begin{theitem}
        \item \(\dom(F\circ G)=\{x\mid x\in\dom F\wedge F(x)\in\dom G\}\)
        \item \(\forall x\in\dom(F\circ G)\),有\(F\circ G(x)=G(F(X))\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    推论:
    \begin{theitem}
        \item 设\(F,G,H\)均为函数,则\((f\circ G)\circ H\)和\(F\circ(G\circ H)\)都是函数,且\((F\circ G)\circ H=F\circ(G\circ H)\)
        \item 设\(f:A\to B,g:B\to C\),则\(f\circ g:A\to C\),且\(\forall x\in A\)有\(f\circ g(x)=g(f(x))\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(f:A\to B,g:B\to C\)
    \begin{theitem}
        \item 若\(f:A\to B,g:B\to C\)都是满射,则\(f\circ g:A\to C\)也是满射
        \item 若\(f:A\to B,g:B\to C\)都是单射,则\(f\circ g:A\to C\)也是单射
        \item 若\(f:A\to B,g:B\to C\)都是双射,则\(f\circ g:A\to C\)也是双射
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(f:A\to B\),则\(f=f\circ I_B=I_A\circ f\)
\end{itementry}

\begin{itementry}
    定理:设\(f:A\to B\)是双射,则\(f^{-1}:B\to A\)也是双射
\end{itementry}

\begin{itementry}
    定理:设\(f:A\to B\)是双射,则\(f^{-1}\circ f=I_B,f\circ f^{-1}=I_A\)
\end{itementry}

\section{双射函数与集合的基数}

\begin{itementry}
    等势:设\(A,B\)是集合,若存在\(A\)到\(B\)的双射函数,则称\(A\)与\(B\)是等势的,记为\(A\approx B\),否则记为\(A\not\approx B\)
\end{itementry}

\begin{itementry}
    定理(等势的等价性):设\(A,B,C\)为任意集合
    \begin{theitem}
        \item \(A\approx A\)
        \item \(A\approx B\rightarrow B\approx A\)
        \item \(A\approx B\wedge B\approx C\rightarrow A\approx C\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    康托定理:
    \begin{theitem}
        \item \(\NN\not\approx\RR\)
        \item \(\forall A,A\not\approx P(A)\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    优势\&真优势:
    \begin{theitem}
        \item 设\(A,B\)为集合,若存在从\(A\)到\(B\)的双射函数,则称\(B\)真优势于\(A\),记为\(A\preccurlyeq\hspace{-0.3em}\cdot B\).否则记为\(A\not\preccurlyeq\hspace{-0.3em}\cdot B\)
        \item 设\(A,B\)是集合,若\(A\preccurlyeq\hspace{-0.3em}\cdot B\)且\(A\not\approx B\),则称\(B\)真优势于\(A\),记为\(A\prec\hspace{-0.3em}\cdot B\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(A,B,C\)是任意集合,则
    \begin{theitem}
        \item \(A\preccurlyeq\hspace{-0.3em}\cdot A\)
        \item 若\(A\preccurlyeq\hspace{-0.3em}\cdot B\)且\(B\preccurlyeq\hspace{-0.3em}\cdot A\),则\(A\approx B\)
        \item 若\(A\preccurlyeq\hspace{-0.3em}\cdot B\)且\(B\preccurlyeq\hspace{-0.3em}\cdot C\),则\(A\preccurlyeq\hspace{-0.3em}\cdot C\)
    \end{theitem}
\end{itementry}